package BinaryTree;

/**
 * @author Liaorun
 */
public class BalancedBinaryTree {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static boolean isFull(Node head) {
        ReturnData allInfo = p(head);

        return (1 << allInfo.height - 1) == allInfo.nums;
    }

    private static ReturnData p(Node head) {
        if (head == null) {
            return new ReturnData(0, 0);
        }

        ReturnData leftData = p(head.left);
        ReturnData rightData = p(head.right);

        int height = Math.max(leftData.height, rightData.height) + 1;
        int nums = leftData.nums + rightData.nums + 1;

        return new ReturnData(height, nums);
    }

    /**
     * 递归时候的返回信息
     */
    private static class ReturnData {
        /**
         * 树的高度
         */
        public int height;
        public int nums;

        public ReturnData(int height, int nums) {
            this.height = height;
            this.nums = nums;
        }
    }


    /**
     * 判断是不是平衡二叉树递归时候的返回信息
     */
    public static class ReturnType {
        /**
         * 是否平衡
         */
        public boolean isBalanced;
        /**
         * 树的高度
         */
        public int height;

        public ReturnType(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }


    /**
     * 判断一棵树是不是平衡二叉树
     *
     * @param head 头节点
     * @return
     */
    public static boolean isBalanced(Node head) {
        return process(head).isBalanced;
    }

    /**
     * 判断一棵树是不是平衡二叉树
     *
     * @param x 头节点
     * @return
     */
    public static ReturnType process(Node x) {
        // base
        if (x == null) {
            // 空树是平衡二叉树，高度为0
            return new ReturnType(true, 0);
        }

        // 递归处理左节点
        ReturnType leftData = process(x.left);
        // 递归处理右节点
        ReturnType rightData = process(x.right);

        // 当前节点为头的树的高度 = Math.max(左子树高度，右子树高度） + 1
        int height = Math.max(leftData.height, rightData.height) + 1;

        // 当前树是否平衡 = 左子树是平衡树 && 右子树是平衡树 && 两个子树高度差小于2
        boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height - rightData.height) < 2;

        // 返回当前树的信息
        return new ReturnType(isBalanced, height);
    }
}
